Задача симплексным методом, составить к ней модель двойственной задачи, найти оптимальное решение двойственной задачи.

Задание 1
Путь, связывающий начальное и завершающее события называется полным путем.

Задание 2
Найти два опорных решения системы:
{█(2x_1+3x_3+x_4=6@3x_1-2x_3+x_5=4@x_1+x_2+4x_3=2)┤
Решение
x_4=1,x_5=0
{█(2x_1+3x_3=5@3x_1-2x_3=4@x_1+x_2+4x_3=2)┤
{█(6x_1+9x_3=15@6x_1-4x_3=8@x_1+x_2+4x_3=2)┤
{█(13x_3=7@3x_1=4+2x_3@x_1+x_2+4x_3=2)┤
{█(x_3=7/13@x_1=22/13@x_2=-24/13)┤
x_1=0,x_2=0
{█(3x_3+x_4=6@-2x_3+x_5=4@x_3=1/2)┤
{█(x_4=4,5@x_5=5@x_3=0,5)┤
Задание 3
Решить исходную задачу симплексным методом, составить к ней двойственную, найти оптимальное решение двойственной задачи
Z=2x_1+4x_2→max
{█(x_1+2x_2≤8@-2x_1+3x_2≤6@x_1-x_2≤2)┤
x_1≥0,x_2≥0
Решение
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
x1+2x2+x3 = 8
-2x1+3x2+x4 = 6
x1-x2+x5 = 2
Введем новую переменную x0 = 2x1+4x2.
Выразим базисные переменные <3, 4, 5> через небазисные (свободные).
x0 = 0+2x1+4x2
x3 = 8-x1-2x2
x4 = 6+2x1-3x2
x5 = 2-x1+x2
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
Поскольку коэффициент при переменной x2 больше, чем при остальных переменных, то при увеличении x2 целевая функция будет увеличиваться быстрее.
max(2,4,0,0,0) = 4
x0 = 0+2x1+4x2
x3 = 8-x1-2x2
x4 = 6+2x1-3x2
x5 = 2-x1+x2
В качестве новой переменной выбираем x2.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2 и из них выберем наименьшее:
min (8 : 2 , 6 : 3 , - ) = 2
Вместо переменной x4 в план войдет переменная x2.
Выразим переменную x2 через x4
x2 = 2+2/3x1-1/3x4
и подставим во все выражения.
x0 = 0+2x1+4(2+2/3x1-1/3x4)
x3 = 8-x1-2(2+2/3x1-1/3x4)
x5 = 2-x1+(2+2/3x1-1/3x4)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 8+14/3x1-4/3x4
x3 = 4-7/3x1+2/3x4
x2 = 2+2/3x1-1/3x4
x5 = 4-1/3x1-1/3x4
Полагая небазисные переменные x = (3, 2, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-14/3, 0, 0, 4/3, 0), x0 = 8
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
Поскольку коэффициент при переменной x1 больше, чем при остальных переменных, то при увеличении x1 целевая функция будет увеличиваться быстрее.
max(14/3,0,0,-4/3,0) = 14/3
x0 = 8+14/3x1-4/3x4
x3 = 4-7/3x1+2/3x4
x2 = 2+2/3x1-1/3x4
x5 = 4-1/3x1-1/3x4
В качестве новой переменной выбираем x1.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1 и из них выберем наименьшее:
min (4 : 21/3 , - , 4 : 1/3 ) = 15/7
Вместо переменной x3 в план войдет переменная x1.
Выразим переменную x1 через x3
x1 = 12/7-3/7x3+2/7x4
и подставим во все выражения.
x0 = 8+42/3(12/7-3/7x3+2/7x4)-11/3x4
x2 = 2+2/3(12/7-3/7x3+2/7x4)-1/3x4
x5 = 4-1/3(12/7-3/7x3+2/7x4)-1/3x4
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 16-2x3
x1 = 12/7-3/7x3+2/7x4
x2 = 22/7-2/7x3-1/7x4
x5 = 24/7+1/7x3-3/7x4
Полагая небазисные переменные x = (1, 2, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 2, 0, 0), x0 = 16
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 16-2x3
x1 = 12/7-3/7x3+2/7x4
x2 = 22/7-2/7x3-1/7x4
x5 = 24/7+1/7x3-3/7x4
Оптимальный план можно записать так:
x1 = 15/7, x2 = 31/7
F(X) = 2•15/7 + 4•31/7 = 16
Двойственная задача.
y1-2y2+y3≥2
2y1+3y2-y3≥4
8y1+6y2+2y3 → min
y1 ≥ 0
y2 ≥ 0